class Solution {
    public:
        int numDistinct(string s, string t) {
            int m = s.size(),n = t.size();
            vector<vector<uint64_t>> dp(m+1,vector<uint64_t>(n+1));
            //dp[i+1][j+1] 表示在s的0-i的子串的子序列与t的0-j的子串相等的个数
            //以s的末尾是否参加构成子序列分类
            for(int i = 0 ; i < n+1 ; i++) dp[0][i] = 0;
            for(int j = 0 ; j < m+1 ; j++) dp[j][0] = 1;
            s = " "+s;
            t = " "+t;
            int ret = 0;
            for(int i = 1 ; i < m+1 ; i++){
                for(int j = 1; j < n+1 ; j++){
                    if(s[i] == t[j]){
                        dp[i][j] +=dp[i-1][j-1];
                    }
                    dp[i][j] += dp[i-1][j];
                   
                }
            }
            return dp[m][n];
        }
    };